package com.yin.algorithms;

import com.yin.Sort;
import com.yin.Util;

import java.util.Arrays;

//FIXME BUG
public class RadixSort implements Sort {

    @Override
    public void sort(int[] arr) {

        //数组中元素的最多位数
        int maxBit = getMaxBit(arr);

        //10个桶
        int[][] bucket = new int[10][];

        //位数从1开始
        for(int bit = 1; bit <= maxBit; bit++) {

            //清空储存桶，防止上次循环的影响
            for (int[] curBucket : bucket) {
                curBucket = null;
            }

            //遍历原数组，把元素放入桶内
            for(int i = 0; i < arr.length; i++) {

                //bucket[位数] -> 位数为bit的值的桶
                bucket[getBitValue(arr[i], bit)] = appendChild(bucket[getBitValue(arr[i], bit)], arr[i]);

            }

            System.out.println("---");
            //把桶内元素同步回原数组内
            int pos = 0;
            for(int i = 0; i < bucket.length; i++) {

                if(bucket[i] == null) continue;

                for(int j = 0; j < bucket[i].length; j++) {

                    if(pos == arr.length) break;
                    arr[pos++] = bucket[i][j];
//                    System.out.println(bucket[i][j]);
                }
            }
            System.out.println("---");
        }
    }

    private int[] appendChild(int[] arr, int value) {

        int length = arr == null ? 1 : arr.length + 1;

        int[] result = new int[length];
        result[result.length - 1] = value;

        if (arr != null) System.arraycopy(arr, 0, result, 0, arr.length);

        return result;
    }

    private int getMaxBit(int[] arr) {

        int maxBit = 0;

        for(int cur : arr) {

            int length = String.valueOf(cur).replace("-", "").length();
            if(length > maxBit) maxBit = length;
        }

        return maxBit;
    }

    //返回整型数num的第bit位是什么
    private int getBitValue(int num, int bit) {

        int[] map = {1, 10, 100, 1000, 10000, 100000, 1000000};
        return (Math.abs(num) / map[bit - 1]) % 10;
    }
}
